package _02_greedy_algorithm.coinchange;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/7/19 - 14:58
 * 使用贪心算法解决零钱兑换，可能得不到最优解
 * [15, 10 ,1] 21  就有问题，结果应该是3而不是7
 */
public class Leetcode322_ {
    /**
     * 得出可以凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能组成总金额，得到 -1
     */
    @Test
    public void test1() {
//        Integer[] arr = {5, 2, 1};
        Integer[] arr = {15, 10, 1};
        // 前提需要保证数组有序，从小到大排列
        Arrays.sort(arr, (x, y) -> -Integer.compare(x, y));
        int r = coinChange(arr, 21);
        System.out.println(r);
    }

    private int coinChange(Integer[] coins, int amount) {
        int r = amount;
        int count = 0;

        for (Integer coin : coins) {
            while (r > coin) {
                r -= coin;
                count++;
            }
            if (r == coin) {
                r = 0;
                count++;
                break;
            }
        }
        if (r > 0) {
            return -1;
        }
        return count;
    }
}
